CODv2 3.10 包括的な例題解説

from CODv2 第3章「命令：マシンの言葉」

CODv2 3.10 包括的な例題解説

C 言語で組んだプログラムから MIPS のアセンブリ・コードを導出する

swap 手続き

メモリ中の2つのロケーションの内容を入れ替える C 言語の手続き

swap 手続き

code:exp3.10.1.c

swap(int v[], int k)

{

int temp;

temp = vk;

vk = vk +1 ;

vk + 1 = temp;

}

swap 手続きでのレジスタの割り付け

3.6 コンピュータ・ハードウェア内での手続きのサポート

「手続き呼び出しの間に、保持されるレジスタと保持されないレジスタ」 CODv2 第3章「命令：マシンの言葉」#6850f43e0000000000b18d39

MIPS の規約では手続きへのパラメータの引き渡しに(引数)レジスタ $a0 から $a4 を使用する

swap 手続きではパラメータは v と k の2つを使用する

それぞれに $a0 と $a1 を割り付ける

その他、使用するパラメータは temp

一時レジスタ $t0 を割り付ける

これらのレジスタ割り付けは、この swap 手続きの最初の変数宣言に相当する

swap(int v[], int k)

int temp

!? 変数宣言って、レジスタ割り付けだったのかーー

swap 手続き本体のコード

残りの部分

temp = v[k]

v[k] = v[k+1]

v[k+1] = temp

配列 v[] のベースアドレスから v[k] のアドレスを得るステップ

語のサイズは4バイト

語アドレスは4バイト刻み

インデックスは 0 始まり

インデックス k を4倍する

$t1 に配列 v のベースアドレス

code:exp3.10.1.asm

# 手続き本体

add $t1, $a1, $a1 # パラメータ k ($a1)、k * 2 をレジスタ $t1 に代入

add $t1, $t1, $t1 # k * 4 をレジスタ $t1 に代入

add $t1, $a0, $t1 # パラメータ v ($a0) ［配列 v のベースアドレス］、v + (k * 4) を $t1 に代入

# レジスタ $t1 は vk のアドレスを表す

v[k] と v[k+1] をロード

$t1 を使って v[k] をロードする

$t1 に4を加算して v[k+1] をロードする

code:exp3.10.1.asm

lw $t0, 0($t1) # vk を temp ($t0) へ代入

lw $t2, 4($t1) # vk+1 を一時レジスタ $t2 へ代入

# v[] の次の要素を呼び出し

アドレスを入れ替えてそれぞれの語をストアする

code:exp3.10.1.asm

sw $t2, 0($t1) # vk に一時レジスタ $t2 を代入

sw $t0, 4($t1) # vk+1 に temp ($t0) を代入

戻り

code:exp3.10.1.asm

# 戻り

jr $ra # 呼び出し元のルーチンに戻る

レジスタの退避

これでメモリ領域の割り付け、手続き内容のコーディングが終了

残っているのは swap 手続き内で使用されるレジスタを退避するためのコーディングであるが、このリーフ手続きでは保持すべきレジスタを使用しないので、レジスタを退避する必要がない

手続き呼び出しの間に、保持されるレジスタと保持されないレジスタ CODv2 第3章「命令：マシンの言葉」#6850f43e0000000000b18d39

https://gyazo.com/03013b39454be75c0523f3f015ae11a8

sort 手続き

code:exp3.10.2.c

sort(int v[], int n)

{

int i, j;

for(i = 0; i < n; i = i + 1){

for(j = i - 1; j >= 0 && vj > vj + 1; j = j - 1){

swap(v, j);

}

挿入ソート

ソートの基本アルゴリズムは、バブルソート、挿入ソート、選択ソート

これは「挿入ソート」

https://ja.wikipedia.org/wiki/挿入ソート

挿入ソート（そうにゅうソート、英: insertion sort）あるいは基本挿入法は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。

https://www.codereading.com/algo_and_ds/algo/insertion_sort.html

https://gyazo.com/067032cf26038ad1ef02acd21693f342

swap 手続き CODv2 第3章「命令：マシンの言葉」#68637b870000000000e0f388

swap(v, j) は v[] の j 番目の語と、その次の j+1 番目の語を入れ替える

sort 手続きでのレジスタの割り付け

2つのパラメータ v, n に、引数レジスタ $a0, $a1 を割り付ける

変数 i, j には退避レジスタ $s0, $s1 を割り付ける

sort 手続き本体のコード

2重の for ループと swap 手続きの呼び出しで構成される

swap 手続きにはパラメータが2個、付随する

1番目の for ループ

code:exp3.10.2a.c

for(i = 0; i < n; i = i + 1){ }

for 文の構成は、1)カウンタの初期化、2)ループの終了判定、3)繰り返し時のカウンタ繰り上げ

1)初期化

code:exp3.10.2a.asm

move $s0, $zero # i =0

move は疑似命令( CODv2 第3章「命令：マシンの言葉」#68be8b1d0000000000e708c5 )

2)ループの終了判定

i < n が真でないとき、ループを終了

→ i >= n のとき、ループから抜ける

$s0 < $a1 のとき $t0 に 1 を設定、そうでないときに 0 を設定する

$s0 >= $a1 のときにループを終了する( $t0 が 0 のときループの出口に分岐)

code:exp3.10.2c.asm

for1tst: slt $t0, $s0, $a1 # i >= n ($s0 >= $a1) のとき $t0 = 0

beq $t0, $zero, ext1 # i >= n ($s0 >= $a1) のとき ext1 へジャンプ

ループの最後でループの先頭に戻る

code:exp3.10.2d.asm

j for1tst # 外側のループの最初に戻る

ext1:

3)カウンタ繰り上げ

code:exp3.10.2b.asm

addi $s0, $s0, 1 # i = i + 1

add immediate 命令 ( CODv2 第3章「命令：マシンの言葉」#6874bc5b0000000000769b56 )

1番目の for ループをまとめると

code:exp3.10.2e.asm

move $s0, $zero # i =0

for1tst: slt $t0, $s0, $a1 # i >= n ($s0 >= $a1) のとき $t0 = 0

beq $t0, $zero, ext1 # i >= n ($s0 >= $a1) のとき ext1 へジャンプ

(外側のループの本体)

addi $s0, $s0, 1 # i = i + 1

j for1tst # 外側のループの最初に戻る

ext1:

2番目の for ループ

code:exp3.10.2f.c

for(j = i - 1; j >= 0 && vj > vj + 1; j = j - 1){ }

1)初期化

code:exp3.10.2g.asm

addi $s1, $s0, -1 # j = i - 1 (つまり j = i + (-1) )

3)カウンタ繰り下げ

code:exp3.10.2h.asm

addi $s1, $s1, -1 # j = j - 1 (つまり j = j + (-1) )

2)ループの終了判定

2つの部分からなる

a) j >= 0 の場合

b) v[j] > v[j + 1] の場合

a) , b) 両方の条件が成り立つ場合、ループが継続される

→ a), b) いずれかの条件が満たされない場合、ループから抜ける

a) の条件判定

j >=0 が真でないとき、ループを終了

→ j < 0 のとき、ループから抜ける

$s1 < 0 のとき $t0 に 0 を設定する( slti 命令 CODv2 第3章「命令：マシンの言葉」#688318520000000000d1423a )

code:exp3.10.2i.asm